/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        297.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/15 22:40
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
#include "../header.h"
//序列化是将一个数据结构或者对象转换为连续的比特位的操作，
//进而可以将转换后的数据存储在一个文件或者内存中，
//同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
//
//请设计一个算法来实现二叉树的序列化与反序列化。
//这里不限定你的序列 / 反序列化算法执行逻辑，
//你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
//
//提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅LeetCode 序列化二叉树的格式。
//你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode *root) {
        if (root == nullptr)
            return "X";
        auto l = "(" + serialize(root->left) + ")";
        auto r = "(" + serialize(root->right) + ")";
        return l + to_string(root->val) + r;
    }

    // Decodes your encoded data to tree.
    TreeNode *deserialize(string data) {
        int ptr = 0;
        return parse(data, ptr);
    }

private:
    TreeNode *parse(const string &data, int &ptr) {
        if (data[ptr] == 'X') {
            ++ptr;
            return nullptr;
        }
        auto cur = new TreeNode(0);
        cur->left = parseSubtree(data,ptr);
        cur->val = parseInt(data,ptr);
        cur->right = parseSubtree(data,ptr);
        return cur;
    }

    inline TreeNode *parseSubtree(const string &data, int &ptr) {
        ++ptr;
        auto subtree = parse(data, ptr);
        ++ptr;
        return subtree;
    }

    inline int parseInt(const string &data, int &ptr) {
        int x = 0, sgn = 1;
        if (!isdigit(data[ptr])) {
            sgn = -1;
            ptr++;
        }
        while (isdigit(data[ptr])) {
            x = 10 * x + data[ptr] - '0';
            ptr++;
        }
        return x * sgn;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
